/*
 * CopyRight(C) Kenbin
 */

#ifndef LWS_CHMM_INCLUDED
#define LWS_CHMM_INCLUDED

#include <string>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <fstream>

using namespace std;

/* Comment#
   整个分词可以分为三个阶段:
   1、词语粗切分
   2、切分排歧与未登录词识别
   3、词性标注

   人名、地名的未登录词识别和词性标注可以转化为隐马尔科夫模型进行求解.

   从零开始介绍隐马尔科夫模型.

   人们通常习惯寻找一个事物在一段时间内的变化模式(规律).任何领域中的一
   系列事件都有可能产生有用的模式.

   1、确定性模式

   考虑一套交通信号灯,灯的颜色变化序列依次为:红色-绿色-黄色-红色.这个
   序列可以作为一个状态机器,交通信号灯的不同状态都紧跟着上一个状态.

   每一个状态都唯一依赖于前一个状态,如果交通灯为绿色,那么下一个颜色状
   态将始终为黄色,这个系统是确定性的,生成的模式是确定的.

   2、非确定性模式

   考虑天气状况,天气有晴、多云和下雨三种状态.这三个天气状态之间的变化
   是不确定的,对这个系统建模生成一个天气变化模式(规律),一种做法是假设
   模型的当前状态仅仅依赖于前面的几个状态,这被称为马尔科夫假设,它极大
   的简化了问题.

   一个马克尔夫过程是状态间的转移仅依赖于前n个状态的过程.这个过程被称
   为n阶马尔科夫模型,n是影响下一个状态选择的前n个状态.最简单的马尔科夫
   过程是一阶模型,它的状态选择仅与前一个状态有关.它与确定性系统不同,
   因为下一个状态的选择由相应的概率决定,并不是确定的.

   对于有M个状态的一阶马尔科夫模型,共有M*M个状态转移,因为任何一个状态
   有可能是所有状态的下一个转移状态.每一个转移都有一个概率值,称为状态
   转移概率,这是从一个状态转移到另一个状态的概率.所有的M*M个概率可以用
   一个状态转移矩阵表示.注意这些概率并不随时间变化而改变(这是一个非常
   重要但是不符合实际的假设).
                                  Today
                        sun       cloud       rain
               sun      0.50      0.375       0.125
   Yesterday   cloud    0.25      0.125       0.625
               rain     0.25      0.375       0.375
  (如果昨天是晴天,那么今天是晴天的概率为0.50,注意每一行的概率之和为1)

   要初始化这样一个系统,我们需要确定起始日天气的情况,定义一个初始概率
   向量,称为pi向量:
     sun    cloud     rain
   ( 1.0     0.0       0.0 ) 

   现在定义了一个一阶马尔科夫过程如下:

   状态:        晴天、多云、雨天
   pi向量:      定义系统初始化时每一个状态的概率
   状态转移矩阵:给定前一天天气情况下的当前天气概率

   任何一个可以用这种方式描述的系统都是一个马尔科夫过程.

   3、隐藏模式

   正常情况下,天气状况并不能观察出来,但是可以通过观察水藻的状态来预测
   天气的状态,水藻状态和天气状态有一定的概率关系,在这个例子中有两组状
   态,观察的状态(水藻状态)和隐藏的状态(天气状态),我们希望设计一种算法,
   再不能够直接观察天气的情况下,通过水藻和马尔科夫假设来预测天气.

   隐藏状态和观察状态的数目可以是不同的,观察到的状态序列与隐藏过程有
   一定的概率关系,我们使用隐马尔科夫模型对这个过程建模,这个模型包含了
   一个底层隐藏的马尔科夫过程,以及一个与隐藏状态某种程度相关的可观察
   到的状态集合.

   在隐马尔科夫模型中,隐藏状态有一个一阶马尔科夫过程描述,它们之间都相
   互联系,由状态转移矩阵描述.

   隐藏状态和观察状态之间的联系通过一个混淆矩阵描述,它包含了给定一个
   隐藏状态后得到的观察状态的概率:
                                  Seaweed
                        dry       dryish      damp        soggy
               sun      0.60      0.20        0.15        0.05
   weather     cloud    0.25      0.25        0.25        0.25
               rain     0.05      0.10        0.35        0.50
   (注意矩阵的每一行之和为1)

   4、隐马尔科夫模型

   HMM包含两组状态集合和三组概率集合:

   隐藏状态:    一个系统的真实状态,可以由一个马尔科夫过程描述
   观察状态:    在这个过程中可视的状态
   pi向量:      包含了模型在时间t=1时的一个特殊的隐藏状态的概率(初始概率)
   状态转移矩阵:包含了一个隐藏状态到另一个隐藏状态的概率
   混淆矩阵:    包含了给定隐马尔科夫模型的某一个特殊的隐藏状态,观察到
                的某个观察状态的概率

   5、HMM的应用

   HMM的应用主要是求解三类问题:

   1、给定HMM求一个观察序列的概率(评估)
   2、搜索最有可能生成一个观察序列的隐藏状态序列(解码)
   3、给定观察序列生成一个HMM(学习)

   运用动态规划的技术,这三个问题分别可以用前向算法、维特比算法和前向-后向
   算法求解.

   对于未登录词识别和词性标注来说,其应用主要是后两个,从可观察的词序列中搜
   索隐藏的词性标签和人名、地名的标签,当然,在求解这个问题之前,首先要从语料
   库中学习训练HMM,对于没有标注好的语料库,可以采用前向-后向算法学习,但对于
   标注好的语料库,可以直接使用统计方法生成HMM,更准确也更简单快速.

   未登录词识别和词性标注就是利用维特比算法搜索最有可能生成观察序列的隐藏
   状态序列即解码的问题.
*/

namespace LWS {

    class CTrainHmm
    {
	public:
	    CTrainHmm(int total_observe, int total_state);

	    void TrainStartAndTrans(const char *corpus_file);
	    virtual void TrainEmit(const char *corpus_file);

	    void OutputStartAndTrans(const char *start_and_trans_file);
	    void OutputEmit(const char *emit_binfile, const char *emit_txtfile);

	protected:
	    virtual void convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs) = 0;

	    int m_total_observe;
	    int m_total_state;

	    vector<float> m_start_prob;
	    vector<vector<float> > m_trans_prob;
	    vector<map<short, float> > m_emit_prob;
	    vector<float> m_total_emits;
    };

    class CTrainPerson : public CTrainHmm
    {
	public:
	    CTrainPerson(int total_observe, int total_state);

	    void TrainEmit(const char *corpus_file);
	    void Output(const char *person_name_file);

	private:
	    void convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs);
	    void add_role(string &person_name, int pos, int role_tag);
	    int observe_index(string &observe_desc);

	    enum RoleTags
	    {
		PER_SURNAME = 0,/* 中国人名的姓 */
		PER_GIVEN_SINGLE,/* 中国两字人名的名 */
		PER_GIVEN_FIRST,/* 中国三字人名的名的第一个字 */
		PER_GIVEN_SECOND,/* 中国三字人名的名的第二个字 */
		PER_TRANS_BEGIN,/* 外国人名的首字 */
		PER_TRANS_MIDDLE,/* 外国人名中间的字 */
		PER_TRANS_END,/* 外国人名结尾的字 */
		PER_PRE,/* 人名的上文 */
		PER_NEXT,/* 人名的下文 */
		OTHER
	    };

	    set<string> m_person_name;
    };

    class CTrainLocation : public CTrainHmm
    {
	public:
	    CTrainLocation(int total_observe, int total_state);

	    void TrainEmit(const char *corpus_file);
	    void Output(const char *location_name_file);

	private:
	    void convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs);
	    void add_role(string &location_name, int pos, int role_tag);
	    int observe_index(string &observe_desc);

	    enum RoleTags
	    {
		LOC_BEGIN = 0,/* 地名的首字 */
		LOC_MIDDLE,/* 地名中间的字 */
		LOC_END,/* 地名结尾的字 */
		LOC_PRE,/* 地名的上文 */
		LOC_NEXT,/* 地名的下文 */
		OTHER
	    };

	    set<string> m_location_name;
    };

    class CTrainPosTag : public CTrainHmm
    {
	public:
	    CTrainPosTag(const char *word_file, const char *postag_file, int total_observe, int total_state);
	    void TrainEmit(const char *corpus_file);

	private:
	    void convert_alineofcorpus(string &line, vector<pair<int, short> >&os_pairs);
	    int observe_index(string &observe_desc);
	    int postag_index(string &postag_desc);

	    enum PosTags
	    {
		Ag = 0,/* 形语素,形容词性语素 */
		a,/* 形容词 */
		ad,/* 副形词,直接作状语的形容词 */
		an,/* 名形词,具有名词功能的形容词 */
		b,/* 区别词 */
		c,/* 连词 */
		Dg,/* 副语素,副词性语素 */
		d,/* 副词 */
		e,/* 叹词 */
		f,/* 方位词 */
		g,/* 语素,绝大多数语素都能作为合成词的"词根" */
		h,/* 前接成分 */
		i,/* 成语 */
		j,/* 简称略语 */
		k,/* 后接成分 */
		l,/* 习用语,习用语尚未成为成语,有点"临时性" */
		m,/* 数词 */
		Ng,/* 名语素,名词性语素 */
		n,/* 名词 */
		nr,/* 人名 */
		ns,/* 地名 */
		nt,/* 机构团体 */
		nx,/* 字符串 */
		nz,/* 其他专有名词 */
		o,/* 拟声词 */
		p,/* 介词 */
		q,/* 量词 */
		r,/* 代词 */
		s,/* 处所词 */
		Tg,/* 时语素,时间词性语素 */
		t,/* 时间词 */
		u,/* 助词 */
		Vg,/* 动语素,动词性语素 */
		v,/* 动词 */
		vd,/* 副动词,直接作状语的动词 */
		vn,/* 名动词,指具有名词功能的动词 */
		w,/* 标点符号 */
		x,/* 非语素字,非语素字只是一个符号 */
		y,/* 语气词 */
		z/* 状态词 */
	    };

	    map<string, int> m_word_wordid;
	    map<string, int> m_postag_posidx;
    };

    class CHmm
    {
	public:
	    bool LoadStartAndTrans(const char *start_and_trans_file, int total_state);
	    bool LoadEmit(const char *emit_binfile);

	    float StartProb(short state);
	    float TransProb(short state1, short state2);
	    float EmitProb(int observe, short state);
	    int StateCount(int observe);
	    short StateOfObserve(int observe, int idx);
	    float EmitProbOfObserve(int observe, int idx);

	    int TotalObserve() { return m_total_observe; }

	private:
	    struct EmitNode
	    {
		short state;
		float emit_prob;
	    };

	    int m_total_observe;
	    int m_total_state;

	    vector<float> m_start_prob;
	    vector<vector<float> > m_trans_prob;
	    vector<vector<EmitNode> > m_emit_prob;
    };

    class CHmmAlgo
    {
	public:
	    CHmmAlgo(CHmm *hmm);

	    float GetTransProb(short state1, short state2);
	    float GetEmitProb(int observe, short state);
	    void GetBestStateSequence(vector<int> &observes, vector<short> &best_states);

	    int TotalObserve() { return m_hmm->TotalObserve(); }

	private:
	    struct PathNode
	    {
		float accum_prob;
		short pre;
		short state;
	    };

	    CHmm *m_hmm;
	    vector<vector<PathNode> > m_path_net;
    };

};

#endif
